import java.util.*;

class RandomizedSet {
    Map<Integer,Integer> map;
    List<Integer> list;
    Random random=new Random();
    public RandomizedSet() {
        map=new HashMap<>();
        list=new ArrayList<>();
    }

    public boolean insert(int val) {
        if(map.containsKey(val)){
            return false;
        }
        map.put(val,list.size());
        list.add(list.size(),val);
        return true;
    }

    public boolean remove(int val) {
        if(!map.containsKey(val)){
            return false;
        }
        int tmp=list.get(list.size()-1);
        int index=map.get(val);
        list.set(index,tmp);
        map.put(tmp,index);
        list.remove(list.size()-1);
        map.remove(val);
        return true;
    }

    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }
}








public class project {
    public char findKthBit(int n, int k) {
        StringBuilder sb=new StringBuilder();
        sb.append("0");
        while (sb.length()<k){
            int index=sb.length()-1;
            sb.append("1");
            while (index>=0){
                char ch=sb.charAt(index)=='1'?'0':'1';
                index--;
                sb.append(ch);
            }
        }
        return sb.charAt(k-1);
    }

















    public int longestBeautifulSubstring(String word) {
        int count=1;
        int size=1;
        int max=0;
        for(int i=1;i<word.length();i++){
            char ch=word.charAt(i);
            if(ch>=word.charAt(i-1)){
                size++;
            }
            if(ch>word.charAt(i-1)){
                count++;
            }
            if(ch<word.charAt(i-1)){
                size=1;
                count=1;
            }
            if(count==5){
                max=Math.max(max,size);
            }
        }
        return max;
    }

















//    public int rand10() {
//        int row=0;
//        int col=0;
//        int index=0;
//        do{
//            row=rand7();
//            col=rand7();
//            index=col+(row-1)*7;
//        }while (index>40);
//        return 1+(index-1)%10;
//    }
















    public long smallestNumber(long num) {
        long tmp=num;
        num=Math.abs(num);
        int[] count=new int[10];
        while (num!=0){
            int n=(int)(num%10);
            count[n]++;
            num/=10;
        }
        long ans=0;
        if(tmp>0){
            for(int i=1;i<10;i++){
                if(count[i]!=0){
                    ans=i;
                    count[i]--;
                    break;
                }
            }
            for(int i=0;i<10;i++){
                while (count[i]!=0){
                    count[i]--;
                    ans=ans*10+i;
                }
            }
        }else{
            for(int i=9;i>=0;i--){
                while (count[i]!=0){
                    ans=ans*10+i;
                    count[i]--;
                }
            }
            ans*=-1;
        }
        return ans;
    }
}
